W7. Pushdown Computation Models

Author

Manuel Mazzara

Published

March 5, 2026

1. Theory

1.1 Recap: Finite State Transducers

Before introducing the more powerful Pushdown Transducer, it is important to recall how a Finite State Transducer (FST) works, since a PDT is its direct generalization.

A Finite State Transducer is a Finite State Automaton extended with an output mechanism. Formally, an FST is a tuple where:

  • is a standard FSA (states, input alphabet, transition function, initial state, accepting states);
  • is the output alphabet — the set of symbols that can be written to the output;
  • is the translation function — it maps each state-input pair to an output string.

Key remark: The translation is only applied to strings that are accepted by the underlying FSA. If an input string is rejected, its translation is undefined.

How an FST works: As the FST reads each input symbol, it simultaneously (a) changes state (via ) and (b) writes an output string (via ). The arrow label on a transition diagram is written as input/output, for example a/A means “read from input, write to output.”

Example — Simple case-converter:

Consider (all strings over ) with translation , .

The FST has a single accepting state with self-loops:

  • : read , output
  • : read , output

On input , the FST outputs .

Example — FST with restricted domain:

Consider with the same translation. Now the FST has two states:

  • (accepting): reads and outputs ; if it reads , goes to the non-accepting “sink” state
  • (rejecting): reads any symbol and outputs (because the string will be rejected anyway)

On input , output is . On input , the string is rejected — translation is undefined.

Limitation of FSTs: FSTs, like FSAs, have only fixed, finite memory (the current state). They cannot handle languages requiring counting, such as , where the output must track how many ’s were read to produce the right number of output symbols. We need a Pushdown Transducer.

1.2 Pushdown Transducers (PDTs)
1.2.1 Motivation and Intuition

A Pushdown Transducer (PDT) extends a Pushdown Automaton with an output tape, just as a Finite State Transducer extends an FSA. The PDT can use its stack not only to recognize the language (as in a PDA) but also to assist the translation: the stack stores intermediate information needed to generate the correct output.

The architecture of a PDT consists of four components:

  • Input tape: a read-only tape from which the PDT reads symbols left-to-right
  • Finite state control: a finite set of states with transition logic
  • Stack: a LIFO (last-in, first-out) memory that can grow without bound
  • Output tape: a write-only tape to which the PDT appends output symbols

PDT_arch input Input tape ← read-only → ctrl Finite state control input->ctrl read stack Stack (LIFO) ctrl->stack push/pop output Output tape ← write-only → ctrl->output write

Architecture of a Pushdown Transducer: input tape, finite control, stack, and output tape

The stack is a destructive memory: once a symbol is popped off the stack, it is gone. This is both the source of the PDT’s power and its ultimate limitation.

A transition of a PDT reads an input symbol (or ), inspects the top of the stack, changes state, rewrites the top of the stack, and writes to the output tape — all in one atomic step.

1.2.2 Transition Notation

A transition from state to state is drawn on an arrow and labeled:

where:

  • is the input symbol consumed (or for a silent move)
  • is the stack symbol popped from the top
  • is the string pushed back onto the stack (replacing )
  • is the string written to the output tape

An alternative notation uses a colon to separate the stack part from the output:

Both notations are used in the literature and mean the same thing.

This means that transition and are combined in the diagram as the label .

1.2.3 Formal Definition

A Pushdown Transducer is a 9-tuple:

where:

  • — finite set of states
  • — finite input alphabet
  • — finite stack alphabet
  • — the transition function (partial; maps to finite subsets)
  • — initial state
  • — initial stack symbol (bottom-of-stack marker)
  • — accepting states
  • — finite output alphabet
  • — the translation function (defined only where is defined)

Remarks:

  • are the same components as in a standard “acceptor” PDA.
  • is defined only where is defined — there is no output on undefined transitions.
  • The stack can be necessary for two distinct reasons: (a) the language being recognized requires it, and/or (b) the translation requires it.
1.2.4 Configurations and Transitions

A configuration of a PDT is a 4-tuple:

where:

  • — the current state of the finite control
  • — the unread portion of the input string
  • — the current contents of the stack (top symbol first)
  • — the string already written on the output tape

Transitions between configurations:

  • Input move (consuming symbol ): If and , then:
  • -move (silent, no input consumed): If and , then:

Note the key difference: in an -move, the unread input is unchanged (the PDT consumes no input symbol).

1.2.5 Acceptance Condition

The PDT translates a string to if and only if starting from the initial configuration , the PDT reaches a final configuration with (all input consumed, in an accepting state):

This is defined analogously to how translation works in an FST: the translation of is defined only if the string is accepted.

1.3 PDT Examples
1.3.1 Translating

Consider with translation (capitalize each symbol).

Strategy: Use the stack to count the ’s (push for each ), then verify the ’s while outputting for each matched .

The PDT has states (accepting):

  • : transition — read first , push onto , output
  • : transition — read each additional , push another , output
  • : transition — start reading ’s, pop one , output
  • : transition — each additional , pop one , output
  • : transition — if is on top after consuming all input, accept (no output)

PDT_anbn_AaBb start q0 q₀ start->q0 q1 q₁ q0->q1 a, Z₀/AZ₀, A q1->q1 a, A/AA, A q2 q₂ q1->q2 b, A/ε, B q2->q2 b, A/ε, B q3 q₃ q2->q3 ε, Z₀/Z₀, ε

PDT for translating aⁿbⁿ → AⁿBⁿ

On input : rejected (not in ), translation undefined.

1.3.2 Translating

Consider with translation (output only the -part).

Strategy: During the push phase (reading ’s), output nothing. Only during the pop phase (reading ’s), output for each matched .

  • : and — push ’s with no output
  • : — first , pop one , output
  • : — each additional , output
  • : — accept

Result: .

1.3.3 Translating

Consider with translation (swap the blocks).

Strategy: During the push phase (reading ’s), output (anticipate the output). During the pop phase (reading ’s), output for each matched symbol.

  • : and — push ’s, output for each
  • : — pop , output
  • : — each additional , output
  • : — accept

Result: . This example highlights that the stack enables “inverted” translations not possible with an FST.

1.3.4 Translating (Reverse a String)

Consider with translation (reverse of , where is a separator).

Strategy (PUSH-THEN-POP): While reading , push each symbol onto the stack and output nothing. When the separator is encountered, stop pushing and start popping — outputting each symbol as it is popped. Since the stack is LIFO, popping gives symbols in reverse order.

  • State (PUSH TIME — NO OUTPUT):
    • ; ;
    • ; ;
  • Transition (STOP PUSH):
    • ;
  • State (POP TIME — OUTPUT GENERATED):
    • ;
  • Transition (accepting):

PDT_reverse start q0 q₀ (PUSH) start->q0 q0->q0 a|b: push, no output q1 q₁ (POP) q0->q1 c, A/ε,a | c, B/ε,b q1->q1 ε,A/ε,a | ε,B/ε,b q2 q₂ q1->q2 ε, Z₀/Z₀, ε

PDT for reversing wc → wᴿ

On input : push , push , then see — pop (output ), pop (output ). Final output: . ✓

This example illustrates a key property: the stack enables translations that require “remembering” the input in order to produce output in a non-left-to-right order.

1.4 Closure Properties of DPDA Languages

We now turn from transducers to a fundamental question in formal language theory: which operations preserve the class of languages recognized by Deterministic Pushdown Automata (DPDAs)?

This is the question of closure properties. A class of languages is closed under an operation if applying to languages in always produces a language that is also in .

Formally: is closed under if for any , we have .

Motivation: For regular languages (recognized by FSAs), the class is closed under all four standard operations — union, intersection, complement, and difference. We want to know whether deterministic context-free languages (DPDAs) enjoy the same nice properties.

closure_overview FSA FSA: ∪✓ ∩✓ \✓ ᶜ✓ DPDA DPDA: ∪✗ ∩✗ \✗ ᶜ✓ FSA->DPDA

Closure properties: FSA vs DPDA

Spoiler (summary table):
FSA (Regular) yes yes yes yes
DPDA (Det. CFL) no no no yes

We now examine each operation in turn and understand why the result is what it is.

1.4.1 Closure Under Union: NO

Claim: DPDA is not closed under union.

Counterexample: Consider the following two languages over :

Both and are individually recognizable by DPDAs (each is a deterministic context-free language). However, their union:

cannot be recognized by any DPDA.

Why? The intuitive reason is the stack preparation problem. When a DPDA reads the ’s, it must decide in advance — during the push phase — whether to prepare the stack to match ’s (for ) or ’s (for ). But this decision can only be made after reading all the ’s and then seeing the ’s. By that point, the stack content is already fixed. A nondeterministic PDA could explore both possibilities in parallel, but a deterministic one cannot.

More precisely: after reading , the DPDA’s stack contains some encoding of . When it starts reading ’s, it cannot simultaneously try to match them against (for ) and (for ) — it must commit to one interpretation. If it commits to and the string belongs to (or vice versa), it fails.

Contrast with regular languages: For FSAs, taking the union is easy — build the cross-product automaton and accept if either component accepts. For DPDAs, no analogous construction works in general because the stack contents for and may be incompatible.

DPDA is NOT closed under .

1.4.2 Closure Under Intersection: NO

Claim: DPDA is not closed under intersection.

Counterexample: Consider languages over :

Both are recognizable by DPDAs:

  • : count ’s, match ’s one-for-one, then accept any positive number of ’s.
  • : skip any positive number of ’s, then count ’s, match ’s one-for-one.

Their intersection:

This is the classic language , which is not recognized by any PDA (not even a nondeterministic one), as provable via the Bar-Hillel (Pumping) Lemma for context-free languages. Therefore it certainly cannot be recognized by a DPDA.

DPDA is NOT closed under .

Proof via complement: There is also an algebraic way to see this, using De Morgan’s law:

Since DPDA is closed under complement (see below), if it were also closed under intersection, it would be closed under union — but we just showed it is not. Contradiction.

1.4.3 Closure Under Complement: YES

Claim: DPDA is closed under complement.

Theorem: If , then .

Why complement works for DPDA but not NPDA: For nondeterministic PDAs, complementation fails because a string might be rejected on all computation paths but accepted on some — the nondeterminism makes it hard to “flip” the acceptance condition. For deterministic PDAs, each input leads to exactly one computation, so we can cleanly distinguish accepted from rejected strings.

Construction sketch — why simply swapping final states does not work:

For FSAs, complementing is simple: swap final and non-final states. For PDAs, this naive approach fails because of -moves. Consider: the PDA with input ends in a non-final state , but could reach a final state via an -move. If we flip states, becomes final, so the complemented PDA also accepts — meaning both the original and its “complement” accept . This is wrong.

Correct construction — three steps:

  1. Eliminate loops: Ensure the DPDA is acyclic — it always reads the entire input string and then stops, with no -moves possible after the last input symbol is consumed. Every DPDA can be transformed into an equivalent acyclic DPDA (this is a non-trivial but provable fact). This prevents the -move problem above.
  2. Complete : Make the transition function total by adding a non-accepting “garbage” state for all undefined transitions. After this, the DPDA is a total function from configurations to configurations.
  3. Swap final and non-final states: Now that the machine always halts on a well-defined state after reading the entire input (with no -move ambiguity), swapping accepting and non-accepting states correctly complements the language.

Why acyclicity matters: Without eliminating -loops, after reading the entire input string, the DPDA might loop forever through -moves, passing through some final and some non-final states. With acyclicity, once all input is consumed, the DPDA is in a single well-defined state, and swapping acceptance correctly inverts the language.

DPDA IS closed under .

1.4.4 Closure Under Difference: NO

Claim: DPDA is not closed under difference (set subtraction).

Proof by contradiction: Suppose DPDA were closed under . We know that for any sets :

Since DPDA is closed under complement, whenever . If DPDA were also closed under , then , which means . But we proved DPDA is not closed under intersection. Contradiction!

Therefore DPDA is not closed under .

DPDA is NOT closed under .

Comparison with regular languages: Regular languages (FSA) are closed under all four operations. Deterministic context-free languages have a more asymmetric closure profile — they are only closed under complement, but not under union, intersection, or difference.

1.5 The Bar-Hillel Lemma (Pumping Lemma for CFLs)

The Bar-Hillel Lemma is the generalization of the Pumping Lemma from regular languages to context-free languages. Just as the Pumping Lemma for regular languages gives a necessary condition for regularity, Bar-Hillel gives a necessary (but not sufficient) condition for being a context-free language.

Bar-Hillel Lemma: If is a context-free language (recognized by some NPDA), then there exists such that every with can be written as:

satisfying:

  1. (the “pumped” parts are not both empty)
  2. (the pumped region is bounded)
  3. for all (pumping any number of times stays in )

Note: unlike the regular Pumping Lemma (which pumps one substring ), Bar-Hillel pumps two substrings simultaneously — and — always by the same amount . This reflects the nested structure of context-free derivations.

Application — proving is not a CFL:

The language is not recognized by any PDA (not even nondeterministic). This can be proved using the Bar-Hillel Lemma:

Assume for contradiction that is a CFL. Let be the Bar-Hillel constant. Choose . For any decomposition with and :

  • The region is short (length ), so it can span at most two of the three blocks (’s, ’s, ’s).
  • Pumping up () increases the counts of at most two symbol types, but not all three equally.
  • Therefore has unequal counts of ’s, ’s, and ’s — it is not in .

Contradiction. So is not context-free.

1.6 The Stack as Destructive Memory and Limits of PDAs
1.6.1 Destructive vs. Persistent Memory

A key insight about PDAs is that the stack is a destructive memory: once a symbol is popped off the stack, it is irrecoverably gone. This is precisely why:

  • A PDA can recognize : push symbols while reading ’s, then pop one per .
  • A PDA cannot recognize : to check the ’s, it needs to know again — but the stack was already emptied verifying the ’s.

To overcome this limitation, one needs persistent (read/write) memory — a device that can read a memory location without destroying it. This is the motivation for Turing Machines, which use an unbounded read/write tape instead of a stack.

1.6.2 The Language Hierarchy

lang_hierarchy reg Regular Languages (FSAs) cfl Context-Free Languages (PDAs) reg->cfl  e.g. aⁿbⁿ is CFL,  not regular re Recursively Enumerable (Turing Machines) cfl->re  e.g. aⁿbⁿcⁿ is RE,  not CFL

Language hierarchy: Regular languages ⊂ Context-Free ⊂ Recursively Enumerable

The hierarchy of languages recognized by different computational models is:

  • Regular languages ⊂ Context-free languages (CFLs) ⊂ Recursively enumerable languages (all TM-computable languages)

Examples that illustrate the boundaries:

  • : not regular (proved by Pumping Lemma), but context-free (recognized by a PDA)
  • : not context-free (proved by Bar-Hillel), but computable by a Turing Machine
  • : context-free (recognized by an NPDA) but not a deterministic context-free language
1.7 Why PDAs Are at the Heart of Compilers

PDAs are not merely theoretical constructs — they have direct, practical applications in software engineering, particularly in compiler construction.

1.7.1 PDA and Compilers

The stack memory in a PDA has a LIFO (Last-In, First-Out) policy. This is precisely the right structure for analyzing nested syntactic structures, such as:

  • Arithmetic expressions with parentheses: (a + (b * c))
  • Block-structured programs with begin/end or {/}
  • Function call chains with activation records (each call pushes a frame, each return pops it)

The general structure of a compiler proceeds through several phases:

  • Lexical Analysis: recognizes tokens (identifiers, keywords, operators) — modeled by FSAs
  • Syntax Analysis (Parsing): recognizes the grammatical structure of programs — modeled by NPDAs (context-free grammars describe most programming language syntax)
  • Semantic Analysis, Code Generation, Optimization: further processing

This is why the syntax of almost all programming languages is defined by a context-free grammar, and why parsers (the software that performs syntax analysis) are essentially pushdown automata.

1.7.2 Fixed vs. Unbounded Memory

A crucial conceptual distinction separates FSAs from PDAs:

  • FSA: fixed (bounded) memory — the machine has a finite number of states, period. It cannot count to an arbitrary .
  • PDA: finite but unbounded memory — the machine has a finite set of states, but the stack can grow without bound. It can count to any by pushing symbols.

For example, requires counting an arbitrary . An FSA with any fixed number of states will fail for . A PDA, by using its unbounded stack, succeeds for all .

1.8 Automata Theory and Models of Computation
1.8.1 What is Automata Theory?

Automata theory is the branch of theoretical computer science that studies:

  • Abstract mathematical machines (automata) and their computational properties
  • The computational problems that can be solved by various types of automata

The word automaton (plural: automata) comes from the Greek αὐτόματον, meaning “self-moving” — something that acts by itself. The word was first used by Homer (describing automatic door opening and self-moving statues in ancient Greek epic poetry).

1.8.2 Why Study Automata Theory?
  • An automaton is a finite representation of a formal language that may be infinite — a finite machine can describe infinitely many strings.
  • Automata serve as theoretical models for computing machines, enabling rigorous proofs about computability and complexity.
  • They have direct practical applications: compiler design, model checking, protocol verification, pattern matching.
1.8.3 Models of Computation

A model of computation describes how outputs are computed from inputs, and how computational units, memories, and communications are organized. Different models capture different levels of computational power:

Sequential models:

  • Finite State Automata (FSA) — limited expressiveness, fixed memory; suitable for pattern matching and “brute-force” analysis (model checking)
  • Pushdown Automata (PDA) — adds a stack; can handle nested structures; basis for parsing
  • Turing Machine — unlimited read/write tape; the most general model of sequential computation

Functional models:

  • Lambda calculus — computation via function application and reduction

Concurrent models:

  • Petri nets — for modeling concurrent, distributed systems

This list is not exhaustive — there are many other models (register machines, cellular automata, etc.).

1.8.4 Applications of FSAs in Practice

FSAs (Finite State Automata) have wide practical applications:

  • Moore/Mealy machines model digital circuits and electronic devices
    • Mealy machines are essentially finite state transducers (FSTs) — they produce output on transitions
  • Lexical analysis in compilers: FSAs recognize tokens (the “words” of a programming language)
  • UML state machines: the Unified Modeling Language uses FSA-based notation for describing system behavior (e.g., a temperature controller with states Idle, Heating, Cooling)
  • Protocol modeling: turnstile gates, vending machines, communication protocols can all be modeled as FSAs

The key limitation of FSAs is their fixed memory: they are suitable for patterns that do not require counting or remembering unbounded amounts of data.

2. Definitions

  • Finite State Transducer (FST): A finite state automaton extended with an output mechanism. A 7-tuple where is the output alphabet and is the translation function. Translation is defined only on accepted strings.
  • Pushdown Transducer (PDT): A pushdown automaton extended with an output tape. A 9-tuple where is the output alphabet and is the translation function. The stack can store information needed both for recognition and translation.
  • PDT Configuration: A 4-tuple where is the current state, is the unread input, is the stack contents (top first), and is the output already written.
  • Translation Function (): The component of a PDT (or FST) that specifies what output to write on each transition. means: in state , reading with stack top , write to the output tape. Defined only where is defined.
  • PDT Transition Label: Written as (or ) on a diagram arrow, meaning: read from input, pop , push , write to output.
  • Closure Under an Operation: A class of languages is closed under operation if for any , the result . Closed means: applying the operation stays within the class.
  • DPDA (Deterministic Pushdown Automaton): A PDA where each configuration has at most one possible next configuration: for all , and implies .
  • Deterministic Context-Free Language (DCFL): A language recognized by some DPDA. The class of DCFLs is strictly contained within the class of CFLs.
  • Acyclic PDA: A PDA in which, for every input string , the computation always terminates — i.e., the PDA always reads the entire input and stops, with no -moves possible after all input is consumed. Every DPDA can be transformed into an equivalent acyclic DPDA.
  • Destructive Memory: The characteristic of a stack that once a symbol is popped, it is irrecoverably lost. Contrast with a read/write tape (Turing Machine) where symbols can be read without destroying them.
  • Bar-Hillel Lemma (Pumping Lemma for CFLs): If is a context-free language, then such that any with decomposes as with , , and for all .
  • Automata Theory: The branch of theoretical computer science studying abstract mathematical machines (automata) and the computational problems solvable by them.
  • Model of Computation: A mathematical framework describing how outputs are computed from inputs, and how memory and computation are organized. Examples: FSAs, PDAs, Turing Machines, Lambda calculus, Petri nets.
  • Turing Machine (TM): A model of computation with an infinite read/write tape. More powerful than PDAs because its memory is persistent — reading a cell does not erase it. The most general model of sequential computation.
  • Context-Free Language (CFL): A language recognized by some (nondeterministic) pushdown automaton, or equivalently generated by a context-free grammar. The class of CFLs properly contains all regular languages.

3. Formulas

  • PDT formal definition: where and
  • PDT transition (input move): when and
  • PDT transition (-move): when and
  • PDT acceptance condition: for some
  • Bar-Hillel Lemma: For CFL , such that with , decomposition with , , and
  • Difference via complement: (used to prove non-closure of DPDA under from non-closure under )
  • De Morgan (set version): (used to derive closure/non-closure results)
  • Closure summary for DPDA: closed under only; NOT closed under , , or

4. Practice

4.1. Build a DPDT Translating to (Lab 7, Task 1)

Build a Deterministic Pushdown Transducer that accepts where , and translates it into (keep only ’s and ’s, discarding the excess ’s).

Click to see the solution

Key Concept: Push one per (and output ). During the -phase, pop one per and output — but once the stack is empty (all ’s matched), continue reading remaining ’s without outputting anything.

dpdt_trim_b start q0 q0 start->q0 q0->q0 a, Z₀/AZ₀, a a, A/AA, a q1 q1 q0->q1 b, A/ε, b q1->q1 b, A/ε, b q2 q2 q1->q2 ε, Z₀/Z₀, ε q2->q2 b, Z₀/Z₀, ε

DPDT for translating aⁿbᵐ with n ≤ m into aⁿbⁿ

  1. States: (reading ’s), (reading ’s, stack not yet empty), (reading excess ’s after stack is empty — accepting)

  2. Transitions:

    From To Label Meaning
    Push , output
    Push , output
    First : pop , output
    More ’s: pop , output
    Stack empty: all ’s matched, enter excess phase
    Excess ’s: discard (no output)

  3. Acceptance: is accepting (after -move when stack holds only ). Also need , which is ensured because we must push at least one (no path to without going through ’s push phase).

  4. Trace for (i.e., ):

    • Read : push , output
    • Read : push , output
    • Read : pop , output
    • Read : pop , output
    • -move to (stack has )
    • Read : discard, no output
    • End: accepting. Output: . ✓

Answer: for . Output ’s and the first ’s; discard remaining ’s.

4.2. Build a DPDT Reversing Strings in (Lab 7, Task 2)

Build a Deterministic Pushdown Transducer that recognizes and translates into (the reverse of ).

Click to see the solution

Key Concept: Use the stack’s LIFO property for reversal. Push every character of without outputting anything. When is seen, stop pushing and start popping — outputting each symbol as it is popped (which gives the reverse order).

dpdt_reverse start q0 q0 push start->q0 q0->q0 a, */A*, ε b, */B*, ε q1 q1 pop q0->q1 c, A/ε, a c, B/ε, b q1->q1 ε, A/ε, a ε, B/ε, b q2 q2 q1->q2 ε, Z₀/Z₀, ε

DPDT that reads xc and outputs xᴿ

  1. States: (push phase — reading ), (pop phase — reading and producing output), (accepting)

  2. Transitions:

    From To Label Meaning
    Push , no output
    Push , no output
    Push below , no output
    Push , no output
    Push , no output
    Push below , no output
    See : pop , output
    See : pop , output
    Pop , output
    Pop , output
    Stack empty: accept

  3. Trace for (, ):

    • Push (no output), push (no output)
    • Read : pop , output
    • -move: pop , output
    • -move: see → accept. Output: . ✓

Answer: . Push to stack during push phase; pop during pop phase to output .

4.3. Build a DPDT Translating to (Lab 7, Task 3)

Build a DPDT that accepts and translates it into (drops the trailing ).

Click to see the solution

Key Concept: Output for each leading and push a counter. Output for each . Once ’s are done, pop the stack for each trailing (no output) — if counts match, accept.

dpdt_drop_suffix start q0 q0 start->q0 q0->q0 a, Z₀/AZ₀, a a, A/AA, a q1 q1 q0->q1 b, A/A, b q1->q1 b, A/A, b q2 q2 q1->q2 a, A/ε, ε q2->q2 a, A/ε, ε q3 q3 q2->q3 ε, Z₀/Z₀, ε

DPDT for aⁿbᵐaⁿ → aⁿbᵐ

  1. States: (reading leading ), (reading ), (reading trailing ), (accepting)

  2. Transitions:

    From To Label Meaning
    Leading : push , output
    More leading ’s: push , output
    First : keep stack, output
    More ’s: output , don’t touch stack
    First trailing : pop , no output
    More trailing ’s: pop , no output
    Stack empty: all trailing ’s matched → accept

  3. Trace for :

    • Read : push , output ; read : push , output
    • Read , , : output , , (stack unchanged: )
    • Read : pop , no output; read : pop , no output
    • -move: see → , accept. Output: . ✓

Answer: . Output the leading ’s and ’s; silently consume trailing ’s while verifying the count.

4.4. Build a DPDT Translating to (Lab 7, Task 4)

Build a DPDT that accepts and translates it into (keep only the first ’s, discarding the extra ’s that were “paid for” by ’s).

Click to see the solution

Key Concept: The condition means we need ’s. We output ’s, then match exactly ’s against the pushed ’s (outputting for each), then silently consume the remaining ’s, then verify ’s.

dpdt_ibjc start q0 q0 start->q0 q0->q0 a, Z₀/AZ₀, a a, A/AA, a q1 q1 q0->q1 b, A/ε, b q1->q1 b, A/ε, b q2 q2 q1->q2 b, Z₀/BZ₀, ε q2->q2 b, B/BB, ε q3 q3 q2->q3 c, B/ε, c q3->q3 c, B/ε, c q4 q4 q3->q4 ε, Z₀/Z₀, ε

DPDT for aⁱbʲcᵏ with i + k = j, translating to aⁱbⁱcᵏ

  1. Strategy:

    • Push for each (output ).
    • Match ’s against ’s (pop , output ) — after ’s, stack holds .
    • Continue reading ’s while pushing ’s (no output) — these are the “extra” ’s.
    • Match ’s against ’s (pop , no output) — output for each.
    • Accept when both ’s and ’s are matched.

  2. States: (reading ’s), (reading ’s, matching ’s), (reading extra ’s, pushing ’s), (reading ’s, matching ’s), (accepting)

  3. Transitions:

    From To Label Meaning
    Push , output
    Push , output
    First : pop , output
    More ’s vs ’s: pop, output
    Stack empty ( ’s read): start extra ’s
    More extra ’s: push , no output
    First : pop , output
    More ’s: pop , output
    All matched: accept

  4. Trace for (, and ✓):

    • Push , output
    • Pop , output ; pop , output (2 ’s matched ’s)
    • Push , push (2 extra ’s)
    • Pop , output ; pop , output (2 ’s)
    • See → accept. Output: . ✓

Answer: . Use two stack phases: first pop ’s vs ’s (outputting ), then push ’s for extra ’s, then pop ’s vs ’s (outputting ).

4.5. Build a DPDT Translating to (Lab 7, Task 5)

Build a DPDT that accepts and translates it into .

Click to see the solution

Key Concept: The condition means the number of ’s is between and . Strategy: push two ’s per on the stack (and output once per ). When reading ’s, pop one per and output only when pops bring the stack to exactly or if the remaining count stays within range.

dpdt_range start q0 q0 start->q0 q0->q0 a, */SP*, a q1 q1 q0->q1 b, P/ε, b q1->q1 b, P/ε, b q2 q2 q1->q2 b, S/ε, ε q3 q3 q1->q3 ε, Z₀/Z₀, ε q2->q2 b, S/ε, ε q2->q3 ε, Z₀/Z₀, ε

DPDT for aⁿbᵐ with n ≤ m ≤ 2n, translating to aⁿbⁿ

A simpler approach: push two symbols per , using a two-level pop. For each , pop one symbol. If the stack reaches after between and pops, accept (we’ve consumed enough ’s). The output is regardless.

  • Push phase: For each , push and (two markers). Output .
  • Pop phase: For each , pop one marker. Output only for the first pops.
  • Accept when stack is empty (between and ’s consumed).

Simplified transition design:

States: (reading ’s), (reading ’s, matching first set of ’s — output ), (reading extra ’s, matching second set — no output), (accepting)

Use stack symbols (primary marker — produces output) and (secondary marker — no output). Push then for each .

From To Label Meaning
Push (output) and (silent); output
Push then on existing ; output
Push then on existing ; output
First matching primary: pop , output
More ’s vs : pop, output
vs secondary: pop , no output
More ’s vs : pop, no output
Only ’s consumed (exactly ’s): accept
All markers consumed: accept

Answer: for . Push two stack markers per ; pop one per , outputting only for primary markers; accept when stack is empty.

4.6. DPDA Closure Under Complement — Construction Idea (Lecture 7, Example 1)

Explain why the class of DPDA languages is closed under complement, and outline the construction of the complement DPDA.

Click to see the solution

Key Concept: Complement of a DPDA language is computable by (1) making the DPDA acyclic, (2) completing its transition function, and (3) swapping accepting and non-accepting states.

  1. Why naive state-swapping fails: A DPDA on input may end in a non-accepting state but then take an -move to reach accepting state . If we simply swap states, becomes accepting, so the “complement” DPDA also accepts — which is wrong (both accept , but they should have opposite behavior).
  2. Step 1 — Eliminate loops (make acyclic): Transform the DPDA so that after consuming all input, no further -moves are possible. This ensures the computation halts in a single well-defined state. Every DPDA can be equivalently expressed as an acyclic DPDA (proof omitted; it requires carefully removing -move cycles without changing the accepted language).
  3. Step 2 — Complete : Add a non-accepting “error” state and route all undefined transitions there. Now is a total function: every configuration has exactly one successor.
  4. Step 3 — Swap accepting and non-accepting states: Since the machine is now acyclic and total, it always halts in exactly one state after reading the full input. Swapping and correctly inverts the acceptance: strings that were accepted are now rejected, and vice versa.
  5. Result: The complement DPDA recognizes whenever the original DPDA recognizes . Therefore DPDA is closed under .

Answer: DPDA is closed under complement via the three-step construction: eliminate loops, complete , swap final/non-final states.

4.7. DPDA Closure Under Difference — Proof by Contradiction (Lecture 7, Example 2)

Prove that DPDA is not closed under set difference ().

Click to see the solution

Key Concept: Use the identity and the fact that DPDA is closed under complement to derive a contradiction with non-closure under intersection.

  1. Assume for contradiction that DPDA is closed under .
  2. Use the identity: For any sets :
  3. Apply closure assumptions:
    • Since DPDA is closed under complement (proved): .
    • By the assumed closure under difference: and .
    • Therefore for any .
  4. But: We proved that DPDA is not closed under intersection (using ). Contradiction!
  5. Conclusion: The assumption was wrong. DPDA is not closed under .

Answer: By contradiction using and DPDA’s closure under complement, non-closure under implies non-closure under .

4.8. DPDA Closure Under Union — Counterexample (Lecture 7, Example 3)

Show that the class of languages recognized by DPDAs is not closed under union, using and .

Click to see the solution

Key Concept: Both and are individually recognized by DPDAs, but their union cannot be recognized by any DPDA — because a deterministic machine cannot decide which language to prepare for during the push phase.

  1. Verify : Build a DPDA that pushes one per , then pops one per . Accepts when is on top after all ’s. Standard construction.
  2. Verify : Build a DPDA that pushes two ’s per , then pops one per . Accepts when is on top.
  3. Argue :
    • A DPDA reading must decide in its stack preparation whether it will face or ’s.
    • After the ’s are read, the stack is committed. When the ’s arrive, the machine cannot re-examine the -count.
    • A deterministic machine cannot simultaneously prepare for both ’s and ’s.
    • A formal proof uses the fact that (via Bar-Hillel Lemma) combined with algebraic manipulation.
  4. Conclusion: , so DPDA is not closed under .

Answer: DPDA is not closed under union. The union witnesses this, as neither component alone poses a problem but their union does.

4.9. FST — Translating All Strings Over (Tutorial 7, Example 1)

Build a Finite State Transducer that accepts any string and translates it by the rule , (convert lowercase to uppercase).

Click to see the solution

Key Concept: Since every string is accepted, a single accepting state with self-loops suffices.

fst_upper start q0 q0 start->q0 q0->q0 a/A b/B

One-state FST translating a→A and b→B

  1. Define the FST components:
    • States: ; initial state ; accepting:
    • Input alphabet: ; Output alphabet:
  2. Transitions (both are self-loops on ):
    • : read , write
    • : read , write
  3. Trace for input :
    • Read in : output , stay in
    • Read in : output , stay in
    • Read in : output , stay in
    • End of input; → accepted

Answer: Output . The FST has one state (accepting) with self-loops and .

4.10. FST — Translating Only Strings Without ’s (Tutorial 7, Example 2)

Build a Finite State Transducer that accepts strings containing no ’s, and translates them by , . Strings containing are rejected (translation undefined).

Click to see the solution

Key Concept: Use a sink (non-accepting) state to handle ’s. Once a is seen, the string is rejected regardless of further input.

fst_no_b start q0 q0 start->q0 q0->q0 a/A q1 q1 q0->q1 b/B q1->q1 a/ε b/ε

FST accepting only strings without b’s

  1. States: (accepting — no seen), (non-accepting sink — seen)
  2. Transitions:
    • : read in , output , stay
    • : read in , output , go to sink
    • : read in sink, output nothing
    • : read in sink, output nothing
  3. Trace for : stays in , outputs → accepted, translation =
  4. Trace for : → rejected (translation undefined)

Answer: The FST has states with accepting. Strings without ’s are translated to their uppercase version; strings with ’s are rejected.

4.11. PDT — Translating (Tutorial 7, Example 3)

Build a Pushdown Transducer for that translates each string by , , i.e., .

Click to see the solution

Key Concept: This translation requires a stack because we need to count ’s and then verify ’s. An FST cannot count to an arbitrary .

pdt_upper start q0 q0 start->q0 q1 q1 q0->q1 a, Z₀/AZ₀, A q1->q1 a, A/AA, A q2 q2 q1->q2 b, A/ε, B q2->q2 b, A/ε, B q3 q3 q2->q3 ε, Z₀/Z₀, ε

PDT translating aⁿbⁿ into AⁿBⁿ

  1. States: (start), (reading ’s), (reading ’s), (accepting)

  2. Stack alphabet:

  3. Transitions:

    From To Label Meaning
    First : push , output
    More ’s: push , output
    First : pop , output
    More ’s: pop , output
    Stack empty (only ): accept

  4. Trace for :

    • (output )
    • (output )
    • (output )
    • (output )
    • — ACCEPT

Answer: . The PDT uses a stack to count ’s, then matches ’s one-for-one.

4.12. PDT — Translating (Tutorial 7, Example 4)

Build a Deterministic Pushdown Transducer for with translation (output only the -part, discarding the ’s).

Click to see the solution

Key Concept: During the push phase (reading ’s), output nothing (). Only during the pop phase (reading ’s), output for each pop.

pdt_bn start q0 q0 start->q0 q0->q0 a, */A*, ε q1 q1 q0->q1 b, A/ε, b q1->q1 b, A/ε, b qf qF q1->qf ε, Z₀/Z₀, ε

PDT translating aⁿbⁿ into bⁿ

  1. States: (reading ’s), (reading ’s), (accepting)

  2. Transitions:

    From To Label Meaning
    First : push , NO output
    More ’s: push , NO output
    First : pop , output
    More ’s: pop , output
    Stack empty: accept, no output

  3. Trace for (i.e., … but has 3 ’s and 2 ’s, not in ; use ):

    • Push , push (no output), then pop (output ), pop (output ), see → accept.
    • Output: .

Answer: . The stack counts ’s; output is generated only in the pop phase.

4.13. PDT — Translating (Tutorial 7, Example 5)

Build a DPDT for with translation (swap the two blocks).

Click to see the solution

Key Concept: Output during the push phase (reading ’s), and output during the pop phase (reading ’s). This “swaps” the outputs.

pdt_swap start q0 q0 start->q0 q0->q0 a, */A*, b q1 q1 q0->q1 b, A/ε, a q1->q1 b, A/ε, a qf qF q1->qf ε, Z₀/Z₀, ε

PDT translating aⁿbⁿ into bⁿaⁿ

  1. States: (reading ’s), (reading ’s), (accepting)

  2. Transitions:

    From To Label Meaning
    First : push , output
    More ’s: push , output
    First : pop , output
    More ’s: pop , output
    Done: accept

  3. Trace for :

    • Read : output , push
    • Read : output , push
    • Read : output , pop
    • Read : output , pop
    • See → accept. Output: . ✓

Answer: . Output ’s during push and ’s during pop.

4.14. DPDA — Constructing the DPDA for (Tutorial 7, Example 6)

Build a DPDA that recognizes .

Click to see the solution

Key Concept: Push ’s for each , match ’s against them, then accept any positive number of ’s (the ’s don’t affect the stack count).

dpda_abncm start q0 q0 start->q0 q1 q1 q0->q1 a, Z₀/AZ₀ q1->q1 a, A/AA q2 q2 q1->q2 b, A/ε q2->q2 b, A/ε q3 q3 q2->q3 c, Z₀/Z₀ q3->q3 c, Z₀/Z₀

DPDA for aⁿbⁿcᵐ

  1. States: (start), (reading ’s), (reading ’s), (reading ’s — accepting)

  2. Transitions:

    From To Label Meaning
    First : push
    More ’s: push
    First : pop
    More ’s: pop
    First (stack shows , so ’s matched ’s): enter accepting phase
    More ’s: stay

  3. Acceptance: is the accepting state; reached only when ’s exactly matched ’s and at least one was seen.

Answer: The DPDA with states (accepting) as above recognizes .

4.15. DPDA — Constructing the DPDA for (Tutorial 7, Example 7)

Build a DPDA that recognizes .

Click to see the solution

Key Concept: Skip over the ’s (they don’t constrain anything), then count ’s by pushing to the stack, then verify the ’s by popping.

dpda_am_bnc_n start q0 q0 start->q0 q1 q1 q0->q1 a, Z₀/Z₀ q1->q1 a, Z₀/Z₀ q2 q2 q1->q2 b, Z₀/BZ₀ q2->q2 b, B/BB q3 q3 q2->q3 c, B/ε q3->q3 c, B/ε q4 q4 q3->q4 ε, Z₀/Z₀

DPDA for aᵐbⁿcⁿ

  1. States: (start), (reading ’s), (reading ’s), (reading ’s), (accepting)

  2. Transitions:

    From To Label Meaning
    First : no stack change
    More ’s: no stack change
    First : push
    More ’s: push
    First : pop
    More ’s: pop
    Stack has only : all ’s matched ’s → accept

  3. Acceptance: is accepting, reached via -move when stack shows .

Answer: The DPDA with states (accepting) as above recognizes .

4.16. DPDA Closure Under Intersection — Counterexample (Tutorial 7, Example 8)

Show that using and , and conclude that DPDA is not closed under intersection.

Click to see the solution

Key Concept: Both and are DPDAs (built in previous examples). Their intersection is , which is not even a CFL (provable via Bar-Hillel).

  1. Compute the intersection: (A string belongs to both iff the -count equals the -count AND the -count equals the -count, so all three counts are equal.)
  2. Apply Bar-Hillel Lemma to : Assume it is a CFL. Let be the Bar-Hillel constant. Choose . Any decomposition with spans at most two of the three symbol groups. Pumping up () increases only those two groups, making the counts unequal. Contradiction. So , and thus .
  3. Conclusion: but . Therefore DPDA is not closed under .

Answer: The intersection is not a CFL, so it cannot be recognized by any DPDA. Non-closure under intersection is proved.